﻿// Power Calculus POJ - 3134 训练营.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://vjudge.net/problem/POJ-3134#author=GPT_zh

从 x 开始，反复乘以 x，我们可以用三十次乘法计算出 x31：

x2 = x × x, x3 = x2 × x, x4 = x3 × x, …, x31 = x30 × x.

平方操作可以显著缩短乘法序列。以下是用八次乘法计算 x31 的方法：

x2 = x × x, x3 = x2 × x, x6 = x3 × x3, x7 = x6 × x, x14 = x7 × x7, x15 = x14 × x, x30 = x15 × x15, x31 = x30 × x.

这并不是计算 x31 最短的乘法序列。有很多方法只需七次乘法。以下是其中一种：

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x8 = x4 × x4, x10 = x8 × x2, x20 = x10 × x10, x30 = x20 × x10, x31 = x30 × x.

如果除法也可用，我们可以找到更短的操作序列。有可能用六次操作（五次乘法和一次除法）计算 x31：

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x16 = x8 × x8, x32 = x16 × x16, x31 = x32 ÷ x.

如果除法和乘法一样快的话，这是计算 x31 最有效的方法之一。

你的任务是编写一个程序，找出用乘法和除法计算给定正整数 n 的 xn 所需的最少操作次数。序列中出现的乘积和商应该是 x 的正整数次幂。换句话说，例如 x−3 绝不应出现。

输入
输入是一个或多个行的序列，每行包含一个整数 n。 n 为正整数，且小于或等于 1000。输入以 0 表示结束。

输出
你的程序应该打印计算 xn 所需的最少总乘法和除法次数。这些数字应该分别写在单独的一行上，不应包含任何多余字符，如前导或尾随空格。

1
31
70
91
473
512
811
953
0


0
6
8
9
11
9
13
12
*/
int main()
{
    std::cout << "Hello World!\n";
}

 